Two-phase Commit
   HOME

TheInfoList



OR:

In
transaction processing Transaction processing is information processing in computer science that is divided into individual, indivisible operations called ''transactions''. Each transaction must succeed or fail as a complete unit; it can never be only partially comple ...
,
database In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases sp ...
s, and
computer networking A computer network is a set of computers sharing resources located on or provided by network nodes. The computers use common communication protocols over digital interconnections to communicate with each other. These interconnections are ma ...
, the two-phase commit protocol (2PC) is a type of
atomic commitment protocol Atomic may refer to: * Of or relating to the atom, the smallest particle of a chemical element that retains its chemical properties * Atomic physics, the study of the atom * Atomic Age, also known as the "Atomic Era" * Atomic scale, distances com ...
(ACP). It is a
distributed algorithm A distributed algorithm is an algorithm designed to run on computer hardware constructed from interconnected processors. Distributed algorithms are used in different application areas of distributed computing, such as telecommunications, scientific ...
that coordinates all the processes that participate in a distributed atomic transaction on whether to commit or abort (roll back) the transaction. This protocol (a specialised type of consensus protocol) achieves its goal even in many cases of temporary system failure (involving either process, network node, communication, etc. failures), and is thus widely used. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman (1987)
''Concurrency Control and Recovery in Database Systems''
Chapter 7, Addison Wesley Publishing Company,
Gerhard Weikum Gerhard Weikum is a Research Director at the Max Planck Institute for Informatics in Saarbrücken, Germany, where he is leading the databases and information systems department. His current research interests include transactional and distributed ...
, Gottfried Vossen (2001)
''Transactional Information Systems''
Chapter 19, Elsevier,
Philip A. Bernstein, Eric Newcomer (2009)
''Principles of Transaction Processing'', 2nd Edition
, Chapter 8, Morgan Kaufmann (Elsevier),
However, it is not resilient to all possible failure configurations, and in rare cases, manual intervention is needed to remedy an outcome. To accommodate recovery from failure (automatic in most cases) the protocol's participants use
logging Logging is the process of cutting, processing, and moving trees to a location for transport. It may include skidding, on-site processing, and loading of trees or logs onto trucks or skeleton cars. Logging is the beginning of a supply chain ...
of the protocol's states. Log records, which are typically slow to generate but survive failures, are used by the protocol's
recovery procedure In telecommunication, a recovery procedure is a process that attempts to bring a system back to a normal operating state. Examples: #The actions necessary to restore an automated information system's data files and computational capability after a ...
s. Many protocol variants exist that primarily differ in logging strategies and recovery mechanisms. Though usually intended to be used infrequently, recovery procedures compose a substantial portion of the protocol, due to many possible failure scenarios to be considered and supported by the protocol. In a "normal execution" of any single
distributed transaction A distributed transaction is a database transaction in which two or more network hosts are involved. Usually, hosts provide transactional resources, while the transaction manager is responsible for creating and managing a global transaction that enc ...
(i.e., when no failure occurs, which is typically the most frequent situation), the protocol consists of two phases: #The commit-request phase (or voting phase), in which a coordinator process attempts to prepare all the transaction's participating processes (named participants, cohorts, or workers) to take the necessary steps for either committing or aborting the transaction and to vote, either "Yes": commit (if the transaction participant's local portion execution has ended properly), or "No": abort (if a problem has been detected with the local portion), and #The commit phase, in which, based on voting of the participants, the coordinator decides whether to commit (only if all have voted "Yes") or abort the transaction (otherwise), and notifies the result to all the participants. The participants then follow with the needed actions (commit or abort) with their local transactional resources (also called recoverable resources; e.g., database data) and their respective portions in the transaction's other output (if applicable). The two-phase commit (2PC) protocol should not be confused with the
two-phase locking In databases and transaction processing, two-phase locking (2PL) is a concurrency control method that guarantees serializability.Phil Bernstein, Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman (1987) ''Concurrency Control and Recovery in Dat ...
(2PL) protocol, a
concurrency control In information technology and computer science, especially in the fields of computer programming, operating systems, multiprocessors, and databases, concurrency control ensures that correct results for Concurrent computing, concurrent operations a ...
protocol.


Assumptions

The protocol works in the following manner: one node is a designated coordinator, which is the master site, and the rest of the nodes in the network are designated the participants. The protocol assumes that there is
stable storage Stable storage is a classification of computer data storage technology that guarantees atomicity for any given write operation and allows software to be written that is robust against some hardware and power failures. To be considered atomic, upon ...
at each node with a write-ahead log, that no node crashes forever, that the data in the write-ahead log is never lost or corrupted in a crash, and that any two nodes can communicate with each other. The last assumption is not too restrictive, as network communication can typically be rerouted. The first two assumptions are much stronger; if a node is totally destroyed then data can be lost. The protocol is initiated by the coordinator after the last step of the transaction has been reached. The participants then respond with an agreement message or an abort message depending on whether the transaction has been processed successfully at the participant.


Basic algorithm


Commit request (or voting) phase

#The coordinator sends a query to commit message to all participants and waits until it has received a reply from all participants. #The participants execute the transaction up to the point where they will be asked to commit. They each write an entry to their undo log and an entry to their
redo log Undo is an interaction technique which is implemented in many computer programs. It erases the last change done to the document, reverting it to an older state. In some more advanced programs, such as graphic processing, undo will negate the las ...
. #Each participant replies with an agreement message (participant votes Yes to commit), if the participant's actions succeeded, or an abort message (participant votes No, not to commit), if the participant experiences a failure that will make it impossible to commit.


Commit (or completion) phase


Success

If the coordinator received an agreement message from all participants during the commit-request phase: #The coordinator sends a commit message to all the participants. #Each participant completes the operation, and releases all the locks and resources held during the transaction. #Each participant sends an acknowledgement to the coordinator. #The coordinator completes the transaction when all acknowledgements have been received.


Failure

If any participant votes No during the commit-request phase (or the coordinator's timeout expires): #The coordinator sends a rollback message to all the participants. #Each participant undoes the transaction using the undo log, and releases the resources and locks held during the transaction. #Each participant sends an acknowledgement to the coordinator. #The coordinator undoes the transaction when all acknowledgements have been received.


Message flow

Coordinator                                          Participant
                             QUERY TO COMMIT
                 -------------------------------->
                             VOTE YES/NO             prepare*/abort*
                 <-------------------------------
commit*/abort*               COMMIT/ROLLBACK
                 -------------------------------->
                             ACKNOWLEDGEMENT          commit*/abort*
                 <--------------------------------  
end
An * next to the record type means that the record is forced to stable storage.
C. Mohan Chandrasekaran Mohan is an Indian-born American computer scientist. He was born on 3 August 1955 in Tamil Nadu, India. After growing up there and finishing his undergraduate studies in Chennai, he moved to the United States in 1977 for gradu ...
, Bruce Lindsay and R. Obermarck (1986)
"Transaction management in the R* distributed database management system"
''ACM Transactions on Database Systems (TODS)'', Volume 11 Issue 4, Dec. 1986, Pages 378 - 396


Disadvantages

The greatest disadvantage of the two-phase commit protocol is that it is a blocking protocol. If the coordinator fails permanently, some participants will never resolve their transactions: After a participant has sent an agreement message to the coordinator, it will block until a commit or rollback is received.


Implementing the two-phase commit protocol


Common architecture

In many cases the 2PC protocol is distributed in a computer network. It is easily distributed by implementing multiple dedicated 2PC components similar to each other, typically named
Transaction manager Transaction processing is information processing in computer science that is divided into individual, indivisible operations called ''transactions''. Each transaction must succeed or fail as a complete unit; it can never be only partially comple ...
s (TMs; also referred to as 2PC agents or Transaction Processing Monitors), that carry out the protocol's execution for each transaction (e.g.,
The Open Group The Open Group is a global consortium that seeks to "enable the achievement of business objectives" by developing "open, vendor-neutral technology standards and certifications." It has over 840 member organizations and provides a number of servi ...
's
X/Open XA For transaction processing in computing, the X/Open XA standard (short for "eXtended Architecture") is a specification released in 1991 by X/Open (which later merged with The Open Group) for distributed transaction processing (DTP). Goals The go ...
). The databases involved with a distributed transaction, the participants, both the coordinator and participants, register to close TMs (typically residing on respective same network nodes as the participants) for terminating that transaction using 2PC. Each distributed transaction has an ad hoc set of TMs, the TMs to which the transaction participants register. A leader, the coordinator TM, exists for each transaction to coordinate 2PC for it, typically the TM of the coordinator database. However, the coordinator role can be transferred to another TM for performance or reliability reasons. Rather than exchanging 2PC messages among themselves, the participants exchange the messages with their respective TMs. The relevant TMs communicate among themselves to execute the 2PC protocol schema above, "representing" the respective participants, for terminating that transaction. With this architecture the protocol is fully distributed (does not need any central processing component or data structure), and scales up with number of network nodes (network size) effectively. This common architecture is also effective for the distribution of other
atomic commitment protocol Atomic may refer to: * Of or relating to the atom, the smallest particle of a chemical element that retains its chemical properties * Atomic physics, the study of the atom * Atomic Age, also known as the "Atomic Era" * Atomic scale, distances com ...
s besides 2PC, since all such protocols use the same voting mechanism and outcome propagation to protocol participants.


Protocol optimizations

Database In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases sp ...
research has been done on ways to get most of the benefits of the two-phase commit protocol while reducing costs by protocol optimizations and protocol operations saving under certain system's behavior assumptions.


Presumed abort and presumed commit

Presumed abort or Presumed commit are common such optimizations.
C. Mohan Chandrasekaran Mohan is an Indian-born American computer scientist. He was born on 3 August 1955 in Tamil Nadu, India. After growing up there and finishing his undergraduate studies in Chennai, he moved to the United States in 1977 for gradu ...
, Bruce Lindsay (1985)
"Efficient commit protocols for the tree of processes model of distributed transactions"
''ACM SIGOPS Operating Systems Review'', 19(2),pp. 40-52 (April 1985)
An assumption about the outcome of transactions, either commit, or abort, can save both messages and logging operations by the participants during the 2PC protocol's execution. For example, when presumed abort, if during system recovery from failure no logged evidence for commit of some transaction is found by the recovery procedure, then it assumes that the transaction has been aborted, and acts accordingly. This means that it does not matter if aborts are logged at all, and such logging can be saved under this assumption. Typically a penalty of additional operations is paid during recovery from failure, depending on optimization type. Thus the best variant of optimization, if any, is chosen according to failure and transaction outcome statistics.


Tree two-phase commit protocol

The
Tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
2PC protocol (also called Nested 2PC, or Recursive 2PC) is a common variant of 2PC in a
computer network A computer network is a set of computers sharing resources located on or provided by network nodes. The computers use common communication protocols over digital interconnections to communicate with each other. These interconnections are ...
, which better utilizes the underlying communication infrastructure. The participants in a distributed transaction are typically invoked in an order which defines a tree structure, the invocation tree, where the participants are the nodes and the edges are the invocations (communication links). The same tree is commonly utilized to complete the transaction by a 2PC protocol, but also another communication tree can be utilized for this, in principle. In a tree 2PC the coordinator is considered the root ("top") of a communication tree (inverted tree), while the participants are the other nodes. The coordinator can be the node that originated the transaction (invoked recursively (transitively) the other participants), but also another node in the same tree can take the coordinator role instead. 2PC messages from the coordinator are propagated "down" the tree, while messages to the coordinator are "collected" by a participant from all the participants below it, before it sends the appropriate message "up" the tree (except an abort message, which is propagated "up" immediately upon receiving it or if the current participant initiates the abort). The Dynamic two-phase commit (Dynamic two-phase commitment, D2PC) protocol
Yoav Raz Joab (Hebrew Modern: ''Yōʼav'', Tiberian: ''Yōʼāḇ'') the son of Zeruiah, was the nephew of King David and the commander of his army, according to the Hebrew Bible. Name The name Joab is, like many other Hebrew names, theophoric - deri ...
(1995)
"The Dynamic Two Phase Commitment (D2PC) protocol "
''Database Theory — ICDT '95'', ''Lecture Notes in Computer Science'', Volume 893/1995, pp. 162-176, Springer,
is a variant of Tree 2PC with no predetermined coordinator. It subsumes several optimizations that have been proposed earlier. Agreement messages (Yes votes) start to propagate from all the leaves, each leaf when completing its tasks on behalf of the transaction (becoming ready). An intermediate (non leaf) node sends ready when an agreement message to the last (single) neighboring node from which agreement message has not yet been received. The coordinator is determined dynamically by racing agreement messages over the transaction tree, at the place where they collide. They collide either at a transaction tree node, to be the coordinator, or on a tree edge. In the latter case one of the two edge's nodes is elected as a coordinator (any node). D2PC is time optimal (among all the instances of a specific transaction tree, and any specific Tree 2PC protocol implementation; all instances have the same tree; each instance has a different node as coordinator): By choosing an optimal coordinator D2PC commits both the coordinator and each participant in minimum possible time, allowing the earliest possible release of locked resources in each transaction participant (tree node).


See also

*
Three-phase commit protocol In computer networking and databases, the three-phase commit protocol (3PC) is a distributed algorithm which lets all nodes in a distributed system agree to commit a transaction. It is a more failure-resilient refinement of the two-phase commit p ...
*
Paxos algorithm Paxos ( gr, Παξός) is a Greek island in the Ionian Sea, lying just south of Corfu. As a group with the nearby island of Antipaxos and adjoining islets, it is also called by the plural form Paxi or Paxoi ( gr, Παξοί, pronounced in Engli ...
* Raft algorithm *
Two Generals' Problem In computing, the Two Generals' Problem is a thought experiment meant to illustrate the pitfalls and design challenges of attempting to coordinate an action by communicating over an unreliable link. In the experiment, two generals are only able t ...


References

{{DEFAULTSORT:Two-Phase Commit Protocol Data management Transaction processing